#include "headfiles.h"

using namespace std;


// Contains both nodes
static void containNodesRecur(TNODE *root, TNODE *p, TNODE *q, int *node_num) {
    if (root == NULL) {
        return;
    }

    if (root == p) {
        (*node_num)++;
    }
    
    if (root == q) {
        (*node_num)++;
    }
    else {
        containNodesRecur(root->left, p, q, node_num);
        containNodesRecur(root->right, p, q, node_num);
    }

    return;
}

int containNodes(TNODE *root, TNODE *p, TNODE *q) {
    int node_num = 0;
    containNodesRecur(root, p, q, &node_num);

    return node_num;
}

// There is an assumption that p and q are nodes of 
// the binary tree.
TNODE *leastCommonAncestor(TNODE *root, TNODE *p, TNODE *q) {
    if (root == NULL) {
        return NULL;
    }

    if (root == p || root == q) {
        return root;
    }

    TNODE *l = leastCommonAncestor(root->left, p, q);
    TNODE *r = leastCommonAncestor(root->right, p, q);

    if (l && r) return root;

    return l ? l : r;
}

static TNODE *addNode(TNODE *root, int val, int loc, vector<TNODE *> &node_list) {
    TNODE *n = new TNODE;
    if (n == NULL) {
        return root;
    }

    memset(n, 0, sizeof(TNODE));
    n->val = val;
    node_list.push_back(n);
    if (root == NULL) {
        return n;
    }

    TNODE *cur;
    TNODE *next = root;
    int left;
    do {
        cur = next;
        left = loc & 0x1;
        if (left) {
            next = cur->left;
        }
        else {
            next = cur->right;
        }
        loc = loc >> 1;
    } 
    while (next);

    if (left) {
        cur->left = n;
    }
    else {
        cur->right = n;
    }

    return root;
}

TNODE *createBinaryTree(const char *file, vector<TNODE *> &node_list) {
    fstream fs;
    fs.open(file, iostream::in);
    if (!fs.is_open()) {
        return NULL;
    }

    string str;
    TNODE *root = NULL;
    while (fs >> str) {
        if (str.empty()) {
            break;
        }

        int val = atoi(str.c_str());
        fs >> str;
        if (str.empty()) {
            break;
        }
        int loc = atoi(str.c_str());

        root = addNode(root, val, loc, node_list);
    }

    return root;
}

void destroyBinaryTree(TNODE *root) {
    if (root == NULL) {
        return;
    }

    destroyBinaryTree(root->left);
    destroyBinaryTree(root->right);

    delete root;

    return;
}

void printBinaryTreeLevel(TNODE *root) {
    if (root == NULL) {
        return;
    }

    queue<TNODE *> node_queue;
    node_queue.push((TNODE *)NULL);
    node_queue.push(root);
    int level = 0;

    while (!node_queue.empty()) {
        TNODE *n = node_queue.front();
        if (n == NULL) {
            node_queue.pop();
            if (node_queue.empty()) {
                return;
            }
            node_queue.push((TNODE *)NULL);
            cout << endl;
            cout << "Level " << level << ": ";
            ++level;
            continue;
        }

        cout << n->val << "\t";
        node_queue.pop();
        if (n->left) node_queue.push(n->left);
        if (n->right) node_queue.push(n->right);
    }

    return;
}


void InOrderTraversal(TNODE *root) {
    stack<TNODE *> node_stack;
    stack<int> access_count;

    if (root == NULL) {
        return;
    }

    node_stack.push(root);
    access_count.push(0);

    TNODE *cur;
    while (!node_stack.empty()) {
        TNODE *cur = node_stack.top();
        int ref_count = access_count.top();
        if (ref_count == 0) {
            access_count.pop();
            access_count.push(1);
            if (cur->left) {
                node_stack.push(cur->left);
                access_count.push(0);
            }
        }
        else {
            cout << cur->val << "\t";
            access_count.pop();
            node_stack.pop();

            if (cur->right) {
                node_stack.push(cur->right);
                access_count.push(0);
            }
        }
    }

    return;
}


